iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 23
3
Security

看完眼眶濕濕的App開發者慘烈對抗險惡資安環境血與淚的控訴!系列 第 23

Day 23. 非對稱式加密演算法 - RSA (觀念篇)

  • 分享至 

  • xImage
  •  

RSA 簡介

RSA加密演算法是一種非對稱加密演算法,在公開金鑰加密和電子商業中被廣泛使用。

RSA是由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)在1977年一起提出的。當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。

rsa

圖片來源

RSA 基於數學難題所設計出來的演算法,對極大整數無法進行因數分解的難題,證實 RSA 演算法的可靠性。

觀念/名詞定義

有些幾個觀念和名詞大家小時候就念過了(?) 這邊複習一下

質數 Prime number(素數)

大於1的自然数中,除了1和該数自身外,無法被其他自然数整除的数(也可定義為只有1與該數本身两个正因数的数)。

p.s 大於1的自然數若不是質數,則稱之為合數

5是質數,其正因數只有1與5。

6是個合數,除了1與6外,2與3也是其正因數

互質數(互素數)

如果兩個或兩個以上的整數的最大公因數是 1,則稱它們為互質

8 與 10 的最大公因數是 2,不是 1,因此它們並不互質
又例如 7, 10, 13 的最大公因數是 1,因此它們互質

注意一點,並不需要兩個或兩個以上的數互質,但本身卻不一定是質數;上述例子 10 不是質數,但依然與 13 互質

模指數運算(modular exponentiation

就是先做指數在做模除

指數(這個大家應該都知道)

又稱為指數運算、冪運算(Exponentiation)

表達式為bn 讀作「bn次方」或「bn次冪」。

其中, b稱為底數,而n稱為指數,等同於b自乘n次。

a

模除(會寫程式工程師應該都用過)

又稱模數、取模操作、取模運算等(modulo / modulus),口語稱為除餘

讓m去被n整除,只取所得的餘數作為結果。

以表達式為 『 5 mod 2 』 得到 1 同理 26 mod 6 =2; 28 mod 2 = 0 等等

模指數 (從這後面幾項平常人根本用不到XD )

先做指數運算在做模除運算

mod

b底數 = 4 , n指數為3 m模除 = 3 求 c 運算如下

5^3mod7

歐拉函數 \varphi (n)

是小於或等於n的正整數中與n互質的數的數目

又稱為φ函數

例子:\varphi (8)=4,因為1,3,5,7 有四個質數和8互質。

歐拉/尤拉定理 Euler Theorem)

歐拉定理表明,若 n,a 為正整數,且 n,a 互質,則 img

mod 與1在模n下同餘 , \varphi (n)為歐拉函數。

用簡單的例子。令a = 3n=5,此兩數為互質正整數。

小於等於5的正整數中與5互質的數有4個(1、2、3和4)

所以\varphi (5)=4(詳情見歐拉函數

計算:a^{\varphi(n)} = 3^4 = 81 \equiv 1 \pmod{5} (詳情請看同餘)

同餘 ≡

兩個整數ab,若它們除以正整數m所得的餘數相等,則稱ab對於模m同餘
記作a\equiv b{\pmod {m}}
讀作a同餘於bm,或讀作ab關於模m同餘。

比如26\equiv 14{\pmod {12}}

RSA 簡易運作原理及流程

複習一下前面的章節,公開金鑰密碼系統 (Public-key cryptosystem) 加密跟解密使用不同的金鑰 ,又稱『非對稱式加密系統』(asymmeric cryptosystem )

image-20201003000202682

接收者先產生公鑰(Public-key)及私鑰 (Private-key 或 Secret-key)
非對稱式加密 特性就是 公鑰 加密上鎖後,無法在用公鑰解開,只能用**私鑰** 解鎖

image-20201002235708706

金鑰計算方式

  • 選出兩個較大的質數 pq

  • 計算兩個質數的乘積 n = p × q

  • 計算出小於 n 且與 n 互質的整數個數

    \varphi (n)= (p - 1)(q - 1)

  • 選出一個整數 e (拿來當做公鑰)

    • 選擇條件
      • 1 < e < \varphi (n)
      • e 與 \varphi (n) 互質
  • 計算 d (私鑰)

    • d 與 e 的關係
      • e x d / \varphi (n)餘數為 1
      • 因此 d = e - 1 mod \varphi (n)
  • 可得

    • 公鑰 KU = {e, n}
    • 私鑰 KR = {d, n}

金鑰產生流程

image-20201008170758235

用例子說明

  1. 隨機選擇兩個質數 p 和 q
    • p = 61、q = 53 ,p q的乘積 n =3233 將n轉換為二進制:110010100001
    • n 的二進制長度是12,也就是密鑰長度為12 (一般不會使用這麼短,實際上要使用1024bit 以上)
  2. 求初 n 的歐拉函數 (M)
    • 這裡讓 \varphi (n) = M
    • p = 61、q = 53 則 n =3233 那麼n 的歐拉函數記為 M = (p-1)(n-1) = 60 x 52=3120
  3. 找出大於1 小於 n 的歐拉函數 的整數 e
    • 隨機選擇e為17
  4. 計算出 d
    • 依照上面公式 e和d 的乘積除以歐拉函數(M)的餘數為 1
    • 當 e=17,M =3120,K=1,2,3...時, 17 * d - k * M = 1
    • 求解這個方程找到一組滿足關係的 d 和 k 即可,可證其中一組為(d,k)=(2753,15)。

我們找到了通過隨機選擇的互質的 p和q 計算得到 n、m、e、d,我們把這些數字分為兩組

分別為公鑰組{e, n}和私鑰組 {d, n}

e是公鑰{e, n} = (17,3233)

d 是私鑰 {d, n}==(2753,3233)

加解密方式

由於RSA 演算法式數值的運算,所以開始需要把資料字串化,使用ascii code、unicode code、utf-8編碼等將字串轉換為數字

轉換後數字X 需要小於密鑰組中 n 的長度,如長度大於n則需要進行拆分

就是會常聽到的欲要加密資料太大需要先切割,分組處理就是因為這個原因

加密

x 的 e 次方 除以 n 求餘數 y ,c 為加密的密文

可寫為 enc

x 為明文轉化後的數字,e為公鑰,n 為整數(p * q),y 為密文,mod 模除

解密

y 的 e 次方 除以 n 求餘數 x

可寫為 enc

因此計算出的餘數就可還原 x 明文

y 為密文,d 為私鑰,n 為整數(p * q),x 為密文,mod 模除

RSA 安全性

傳遞的資料 (公開場合傳遞資料)

  • n (計算出正整數)
  • e (公鑰)
  • x (密文)

解密需要資料

  • n (計算出正整數)
  • d (私鑰)
  • x (密文)

由於沒有 d (私鑰)因此無法解密

e (公鑰)反推 d (私鑰)可能性

這時候可能會提問說,那我用 e 去計算出 d 不行嗎?

我們來看看要怎麼反推

  • 從解密公式得知 y 的 e 次方 除以 n 求餘數 x
  • 需要取得 \varphi (n)
  • 歐拉函數需要知道 (p-1) (q-1) ,得知必須先求出 p , q
  • 要從 n 取出 p , q
  • 這又稱為『質因素分解』

假如有人找到一種快速因數分解的演算法的話,那麼用 RSA 加密的訊息就會被破解。

但找到這樣的演算法的可能性是非常小的。至今只有過短的 RSA 金鑰才可能被暴力破解

到目前為止,世界上還沒有任何可靠的攻擊RSA演算法的方式可以破解 1024bit 的金鑰。

因此現今只金鑰長度超過1024bit,即是安全的,但因為 768 bits 被破解威脅到 1024bit 的金鑰

建議至少使用 2048 bit 的金鑰

小結

寫出這篇,讓我重新複習,RSA 有用到演算法

歐拉定理跟歐拉函數那邊確實讓我小卡了一陣子

整理完,也讓我重新對RSA 有更清新個認識,希望這篇有幫助到讀者

參考資料

https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

https://zh.wikipedia.org/wiki/%E4%BA%92%E8%B3%AA

https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4

https://zh.wikipedia.org/wiki/%E5%86%AA

https://kknews.cc/zh-tw/news/88nx8l.html

https://cloud.tencent.com/developer/article/1693368

https://www.itread01.com/content/1544974928.html

http://mslab.csie.asia.edu.tw/~jackjow/courses/992_InfoSecurity/ppts/IS_RSA.pdf

https://www.youtube.com/watch?v=G8ZU6vGymnI&ab_channel=PN777

https://www.codecogs.com/latex/eqneditor.php

https://www.youtube.com/watch?v=D_kMadCtKp8&ab_channel=%E6%9D%8E%E6%B0%B8%E4%B9%90%E8%80%81%E5%B8%88

https://www.youtube.com/watch?v=3xgBnD_VsM8&ab_channel=%E5%BC%B5%E5%A4%A7%E5%93%A5


上一篇
Day 22. 加密演算法要注意的那些毛 (二) - 填充模式
下一篇
Day 24. 非對稱式加密演算法 - 橢圓曲線密碼學 Elliptic Curve Cryptography , ECC (觀念篇)
系列文
看完眼眶濕濕的App開發者慘烈對抗險惡資安環境血與淚的控訴!31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

0
starengram
iT邦新手 3 級 ‧ 2021-07-16 13:30:00

b底數 = 4 , n指數為3 m模除 = 3 求 c 運算如下

下方的方程式是不是錯啦XD

0
kerry50407
iT邦新手 5 級 ‧ 2022-03-22 17:02:46

感謝羊小咩的分享,學到不少!

不過這邊有小錯誤:

解密

y 的 e 次方 除以 n 求餘數 x

這裡應該是 y 的 d 次方喔~


公式:
xᵉ(mod n) = y
yᵈ(mod n) = x

例子 (x 代 98):
98¹⁷(mod 3233) = 2570
2570²⁷⁵³(mod 3233) = 98

我要留言

立即登入留言